Các thuật toán rất cần thiết cho cách máy tính xử lý dữ liệu. Nhiều chương trình máy tính chứa các thuật toán trình bày chi tiết các hướng dẫn cụ thể mà máy tính phải thực hiện — theo một thứ tự cụ thể — để thực hiện một nhiệm vụ cụ thể, chẳng hạn như tính tiền lương của nhân viên hoặc in phiếu điểm của học sinh. Vì vậy, một thuật toán có thể được coi là bất kỳ chuỗi hoạt động nào có thể được mô phỏng bởi một hệ thống hoàn chỉnh Turing. Các tác giả khẳng định luận điểm này bao gồm Minsky (1967), Savage (1987) và Gurevich (2000):

• Minsky: "Nhưng chúng tôi cũng sẽ duy trì, với Turing... rằng bất kỳ thủ tục nào có thể" tự nhiên "được gọi là hiệu quả, trên thực tế, có thể được thực hiện bởi một chiếc máy (đơn giản). Mặc dù điều này có vẻ cực đoan, nhưng những lập luận… ủng hộ nó thì khó có thể bác bỏ ”.[27]
• Gurevich: “… Lập luận không chính thức của Turing ủng hộ luận điểm của ông ấy biện minh cho luận điểm mạnh mẽ hơn: mọi thuật toán đều có thể được mô phỏng bởi máy Turing… theo Savage [1987], thuật toán là một quá trình tính toán được xác định bởi máy Turing".[28]

Máy Turing có thể xác định các quy trình tính toán không kết thúc. Các định nghĩa không chính thức của thuật toán thường yêu cầu thuật toán luôn kết thúc. Yêu cầu này làm cho nhiệm vụ quyết định xem một thủ tục chính thức có phải là một thuật toán không trong trường hợp chung - do một định lý chính của lý thuyết tính toán được gọi là bài toán dừng.

Thông thường, khi một thuật toán được liên kết với xử lý thông tin, dữ liệu có thể được đọc từ nguồn đầu vào, được ghi vào thiết bị đầu ra và được lưu trữ để xử lý thêm. Dữ liệu được lưu trữ được coi là một phần của trạng thái bên trong của thực thể thực hiện thuật toán. Trong thực tế, trạng thái được lưu trữ trong một hoặc nhiều cấu trúc dữ liệu.

Đối với một số quá trình tính toán này, thuật toán phải được xác định chặt chẽ: được chỉ định theo cách nó áp dụng trong mọi trường hợp có thể phát sinh. Điều này có nghĩa là mọi bước có điều kiện phải được xử lý một cách có hệ thống, theo từng trường hợp cụ thể; các tiêu chí cho từng trường hợp phải rõ ràng (và có thể tính toán được).

Bởi vì một thuật toán là một danh sách chính xác của các bước chính xác, thứ tự tính toán luôn quan trọng đối với hoạt động của thuật toán. Các hướng dẫn thường được giả định là được liệt kê rõ ràng và được mô tả là bắt đầu "từ trên cùng" và đi "xuống dưới cùng" —một ý tưởng được mô tả chính thức hơn bằng luồng kiểm soát.

Cho đến nay, cuộc thảo luận về việc chính thức hóa một thuật toán đã giả định các tiền đề của lập trình mệnh lệnh. Đây là quan niệm phổ biến nhất - một quan niệm cố gắng mô tả một nhiệm vụ bằng các phương tiện "máy móc", rời rạc. Duy nhất cho quan niệm về các thuật toán chính thức hóa này là phép toán gán, đặt giá trị của một biến. Nó bắt nguồn từ trực giác của " bộ nhớ " như một bàn di chuột. Dưới đây là một ví dụ về sự phân công như vậy.

Đối với một số quan niệm thay thế về những gì tạo thành một thuật toán, hãy xem lập trình hàm và lập trình logic.

Diễn đạt thuật toán

Các thuật toán có thể được thể hiện bằng nhiều loại ký hiệu, bao gồm ngôn ngữ tự nhiên, mã giả, lưu đồ, biểu đồ drakon, ngôn ngữ lập trình hoặc bảng điều khiển (được xử lý bởi trình thông dịch). Các biểu thức ngôn ngữ tự nhiên của các thuật toán có xu hướng dài dòng và mơ hồ, và hiếm khi được sử dụng cho các thuật toán phức tạp hoặc kỹ thuật. Mã giả, lưu đồ, biểu đồ drakon và bảng điều khiển là những cách có cấu trúc để thể hiện các thuật toán tránh nhiều sự mơ hồ thường gặp trong các câu lệnh dựa trên ngôn ngữ tự nhiên. Các ngôn ngữ lập trình chủ yếu nhằm mục đích thể hiện các thuật toán dưới dạng có thể được thực thi bởi máy tính, nhưng cũng thường được sử dụng như một cách để định nghĩa hoặc tài liệu hóa các thuật toán.

Có thể có nhiều cách biểu diễn khác nhau và người ta có thể thể hiện một chương trình máy Turing nhất định dưới dạng một chuỗi các bảng máy (xem máy trạng thái hữu hạn, bảng chuyển đổi trạng thái và bảng điều khiển để biết thêm), dưới dạng lưu đồ và biểu đồ drakon (xem biểu đồ trạng thái để biết thêm), hoặc như một dạng mã máy thô sơ hoặc mã lắp ráp được gọi là "bộ tứ" (xem máy Turing để biết thêm).

Các đại diện của thuật toán có thể được phân loại thành ba cấp độ được chấp nhận của mô tả máy Turing, như sau:[29]

1. Mô tả cấp cao“… Văn xuôi để mô tả một thuật toán, bỏ qua các chi tiết triển khai. Ở cấp độ này, chúng tôi không cần phải đề cập đến cách máy quản lý băng hoặc đầu từ của nó."2. Mô tả triển khai“… Văn xuôi được sử dụng để xác định cách máy Turing sử dụng đầu vào của nó và cách nó lưu trữ dữ liệu trên băng của nó. Ở cấp độ này, chúng tôi không đưa ra thông tin chi tiết về các trạng thái hoặc chức năng chuyển tiếp. "3. Mô tả chính thứcChi tiết nhất, "mức thấp nhất", đưa ra "bảng trạng thái" của máy Turing.